# 补给(好题, 旅行商问题(Travelling Salesman Problem, TSP))
"""对于一个节点可以重复访问的TSP问题, 可以使用先Floyd算法对图结构进行优化后再计算.
Floyd算法: 对图的所有的节点进行了最短路径的计算, 也就是如果A->C的距离大于A->B->C的距离, 那么就采用A->B->C的距离来代替A->C的距离
"""
import math

from leetcode import test_function as tf


def compute_shortest_paths(nodes, D):
    """
    给定村庄坐标列表 nodes（下标从 0 到 n-1），以及飞行距离上限 D，
    构建图并计算所有点对间的最短飞行距离，如果两点间不能直接飞行，则初始距离为正无穷。
    返回二维数组 cost，其中 cost[i][j] 表示村庄 i 到 j 的最短飞行距离。
    """

    def distance(p, q):
        return math.sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)

    n = len(nodes)
    # 初始化 cost 数组
    cost = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                cost[i][j] = 0
            else:
                d = distance(nodes[i], nodes[j])
                if d <= D:
                    cost[i][j] = d

    # Floyd-Warshall 算法计算所有点对最短路
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if cost[i][k] + cost[k][j] < cost[i][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]
    return cost


def tsp_dp(cost):
    """
    利用 DP 状态压缩求解 TSP 问题：
    给定 cost[i][j] 表示从 i 到 j 的飞行距离，返回最短巡回路径长度，
    巡回路径要求从节点0出发，访问所有节点，最后返回节点0。
    注意这里我们默认总部为 nodes[0]。
    """
    n = len(cost)
    INF = float('inf')
    # dp[mask][i]：已访问节点集合 mask，最后停在 i 的最小距离
    dp = [[INF] * n for _ in range(1 << n)]
    # 初始状态：仅访问 0（总部），并在总部结束
    dp[1][0] = 0

    for mask in range(1 << n):  # 遍历所有的掩码
        for i in range(n):  # i 和 j 的循环遍历所有可能的节点对
            if dp[mask][i] == INF:
                continue
            # 尝试从 i 移动到还未访问的 j
            for j in range(n):
                if mask & (1 << j):  # j 已经访问过. 1<<j 即只有第j位为1, &与运算只有在两数都为1时候返回1, 其余都返回0
                    continue
                new_mask = mask | (1 << j)  # 将第j位置为1. |或运算两数在该位有一个为1即返回1
                if dp[mask][i] + cost[i][j] < dp[new_mask][j]:
                    dp[new_mask][j] = dp[mask][i] + cost[i][j]

    # 最后回到总部（节点0）
    final_mask = (1 << n) - 1
    best = INF
    for i in range(n):
        best = min(best, dp[final_mask][i] + cost[i][0])
    return best


def min_total_flight(nodes, d):
    """
    nodes: List of tuples 表示各村庄坐标，nodes[0] 是总部。
    d: 单次飞行的最大距离。

    返回：完成任务的最少飞行距离。
    """
    # 使用Floyd算法计算所有村庄间最短飞行距离
    cost = compute_shortest_paths(nodes, d)
    # 检查图是否连通（至少总部能到其它每个点）
    n = len(nodes)
    for i in range(n):
        if cost[0][i] == float('inf'):
            # 如果总部与某个村庄无法连通，则任务无解
            return -1
    # 在连通图上求解 TSP 保留2为小数
    return "{:.2f}".format(tsp_dp(cost))


if __name__ == '__main__':
    with open("../../data/2020b_i.in", "r") as file:
        n, d = map(int, file.readline().split())
        nodes = []
        for _ in range(n):
            nodes.append(tuple(map(int, file.readline().split())))

    inp = [{"nodes": [(1, 1), (5, 5), (1, 5), (5, 1)], "d": 10},
           {"nodes": [(1, 1), (4, 5), (8, 5), (11, 1)], "d": 6},
           {"nodes": nodes, "d": d}
           ]
    out = ["16.00", "28.00", "19425.45"]
    tf(min_total_flight, inp, out)
